﻿namespace Huayou.Common
{
    using System;
    using System.Collections;

    public class BinaryTree
    {
        protected BinaryTreeNode cursor;
        private bool isNode = false;
        protected BinaryTreeNode prior;
        protected BinaryTreeNode root;
        protected int size;
        protected bool wentLeft;

        public BinaryTree()
        {
            this.Clear();
        }

        private IEnumerator BinaryTreeTraversal(BinaryTreeNode node, int order)
        {
            TreeTraversal traversal = new TreeTraversal(node, order);
            traversal.SetNode(this.isNode);
            return traversal.GetEnumerator();
        }

        public void Clear()
        {
            this.root = null;
            this.cursor = null;
            this.prior = null;
            this.size = 0;
            this.wentLeft = false;
        }

        public object GetValue()
        {
            return this.cursor.GetValue();
        }

        public bool HasLeft()
        {
            return ((this.cursor != null) && (this.cursor.GetLeft() != null));
        }

        public bool HasRight()
        {
            return ((this.cursor != null) && (this.cursor.GetRight() != null));
        }

        public IEnumerator InOrderTraversal()
        {
            return this.InOrderTraversal(this.root);
        }

        public IEnumerator InOrderTraversal(BinaryTreeNode node)
        {
            return this.BinaryTreeTraversal(node, 2);
        }

        public void Insert(object val)
        {
            if (this.cursor != null)
            {
                throw new SystemException("Insertion does not overwrite value.");
            }
            if (this.prior == null)
            {
                if (this.root != null)
                {
                    throw new SystemException("Insertion at root only allowed in empty tree.");
                }
                this.cursor = this.root = new BinaryTreeNode(val);
            }
            else if (this.wentLeft)
            {
                this.prior.SetLeft(this.cursor = new BinaryTreeNode(val));
            }
            else
            {
                this.prior.SetRight(this.cursor = new BinaryTreeNode(val));
            }
            this.size++;
        }

        public bool IsLeftChild()
        {
            return ((this.cursor != null) && this.cursor.IsLeftChild());
        }

        public bool IsRightChild()
        {
            return ((this.cursor != null) && this.cursor.IsRightChild());
        }

        public bool IsRoot()
        {
            return ((this.root == this.cursor) && (this.root != null));
        }

        public void MoveLeft()
        {
            this.prior = this.cursor;
            this.wentLeft = true;
            this.cursor = this.cursor.GetLeft();
        }

        public void MoveNode(BinaryTreeNode node)
        {
            this.prior = null;
            this.cursor = node;
        }

        public void MoveRight()
        {
            this.prior = this.cursor;
            this.wentLeft = false;
            this.cursor = this.cursor.GetRight();
        }

        public void MoveRoot()
        {
            this.prior = null;
            this.cursor = this.root;
        }

        public void MoveUp()
        {
            this.prior = null;
            this.cursor = this.cursor.GetParent();
        }

        public IEnumerator PostOrderTraversal()
        {
            return this.PostOrderTraversal(this.root);
        }

        public IEnumerator PostOrderTraversal(BinaryTreeNode node)
        {
            return this.BinaryTreeTraversal(node, 3);
        }

        public IEnumerator PreOrderTraversal()
        {
            return this.PreOrderTraversal(this.root);
        }

        public IEnumerator PreOrderTraversal(BinaryTreeNode node)
        {
            return this.BinaryTreeTraversal(node, 1);
        }

        public object Remove()
        {
            if (this.cursor == null)
            {
                throw new SystemException("Node to be removed exists");
            }
            if (this.HasLeft() || this.HasRight())
            {
                throw new SystemException("Node to be removed exists");
            }
            object obj2 = this.cursor.GetValue();
            if (this.IsLeftChild())
            {
                this.MoveUp();
                this.cursor.SetLeft(null);
            }
            else if (this.IsRightChild())
            {
                this.MoveUp();
                this.cursor.SetRight(null);
            }
            else
            {
                this.root = this.cursor = (BinaryTreeNode) (this.prior = null);
            }
            this.size--;
            return obj2;
        }

        public void Reset()
        {
            this.cursor = this.root;
            this.prior = null;
            this.wentLeft = false;
        }

        public IEnumerator ReverseInOrderTraversal()
        {
            return this.ReverseInOrderTraversal(this.root);
        }

        public IEnumerator ReverseInOrderTraversal(BinaryTreeNode node)
        {
            return this.BinaryTreeTraversal(node, -2);
        }

        public IEnumerator ReversePostOrderTraversal()
        {
            return this.ReversePostOrderTraversal(this.root);
        }

        public IEnumerator ReversePostOrderTraversal(BinaryTreeNode node)
        {
            return this.BinaryTreeTraversal(node, -3);
        }

        public IEnumerator ReversePreOrderTraversal()
        {
            return this.ReversePreOrderTraversal(this.root);
        }

        public IEnumerator ReversePreOrderTraversal(BinaryTreeNode node)
        {
            return this.BinaryTreeTraversal(node, -1);
        }

        public void SetNode(bool isNode)
        {
            this.isNode = isNode;
        }

        public void SetValue(object val)
        {
            this.cursor.SetValue(val);
        }

        public bool Valid()
        {
            return (this.cursor != null);
        }

        private class TreeTraversal
        {
            public const int InOrder = 2;
            private bool isNode;
            private IList list;
            protected int order;
            public const int PostOrder = 3;
            public const int PreOrder = 1;
            public const int ReverseInOrder = -2;
            public const int ReversePostOrder = -3;
            public const int ReversePreOrder = -1;
            protected BinaryTreeNode root;

            public TreeTraversal(BinaryTreeNode root)
            {
                this.isNode = false;
                this.list = null;
                this.root = root;
            }

            public TreeTraversal(BinaryTreeNode root, int order) : this(root)
            {
                this.order = order;
            }

            public IEnumerator GetEnumerator()
            {
                this.Init();
                return this.list.GetEnumerator();
            }

            private void Init()
            {
                this.list = new ArrayList();
                switch (this.order)
                {
                    case -3:
                        this.ReversePostOrderTraversal(this.list, this.root);
                        return;

                    case -2:
                        this.ReverseInOrderTraversal(this.list, this.root);
                        return;

                    case -1:
                        this.ReversePreOrderTraversal(this.list, this.root);
                        return;

                    case 2:
                        this.InOrderTraversal(this.list, this.root);
                        return;

                    case 3:
                        this.PostOrderTraversal(this.list, this.root);
                        return;
                }
                this.PreOrderTraversal(this.list, this.root);
            }

            private void InOrderTraversal(IList list, BinaryTreeNode node)
            {
                if (node != null)
                {
                    this.InOrderTraversal(list, node.GetLeft());
                    if (this.isNode)
                    {
                        list.Add(node);
                    }
                    else
                    {
                        list.Add(node.GetValue());
                    }
                    this.InOrderTraversal(list, node.GetRight());
                }
            }

            private void PostOrderTraversal(IList list, BinaryTreeNode node)
            {
                if (node != null)
                {
                    this.PostOrderTraversal(list, node.GetLeft());
                    this.PostOrderTraversal(list, node.GetRight());
                    if (this.isNode)
                    {
                        list.Add(node);
                    }
                    else
                    {
                        list.Add(node.GetValue());
                    }
                }
            }

            private void PreOrderTraversal(IList list, BinaryTreeNode node)
            {
                if (node != null)
                {
                    if (this.isNode)
                    {
                        list.Add(node);
                    }
                    else
                    {
                        list.Add(node.GetValue());
                    }
                    this.PreOrderTraversal(list, node.GetLeft());
                    this.PreOrderTraversal(list, node.GetRight());
                }
            }

            private void ReverseInOrderTraversal(IList list, BinaryTreeNode node)
            {
                if (node != null)
                {
                    this.ReverseInOrderTraversal(list, node.GetRight());
                    if (this.isNode)
                    {
                        list.Add(node);
                    }
                    else
                    {
                        list.Add(node.GetValue());
                    }
                    this.ReverseInOrderTraversal(list, node.GetLeft());
                }
            }

            private void ReversePostOrderTraversal(IList list, BinaryTreeNode node)
            {
                if (node != null)
                {
                    if (this.isNode)
                    {
                        list.Add(node);
                    }
                    else
                    {
                        list.Add(node.GetValue());
                    }
                    this.ReversePostOrderTraversal(list, node.GetRight());
                    this.ReversePostOrderTraversal(list, node.GetLeft());
                }
            }

            private void ReversePreOrderTraversal(IList list, BinaryTreeNode node)
            {
                if (node != null)
                {
                    this.ReversePreOrderTraversal(list, node.GetRight());
                    this.ReversePreOrderTraversal(list, node.GetLeft());
                    if (this.isNode)
                    {
                        list.Add(node);
                    }
                    else
                    {
                        list.Add(node.GetValue());
                    }
                }
            }

            public void SetNode(bool isNode)
            {
                this.isNode = isNode;
            }

            public void SetOrder(int order)
            {
                this.order = order;
            }
        }
    }
}

